(display "\n========================================\n")
(define (entry tree)
    (car tree))

(define (left-branch tree)
    (cadr tree))

(define (right-branch tree)
    (caddr tree))

(define (make-tree entry left right)
    (list entry left right))

(define (tree->list-2 tree)
    (define (copy-to-list tree result-list)
        (if (null? tree)
            result-list
            (copy-to-list (left-branch tree)
                               (cons (entry tree)
                                     (copy-to-list (right-branch tree)
                                                        result-list)))))
    (copy-to-list tree '()))

(define (list->tree elements)
    (define (partial-tree elts n)
        (if (= n 0)
            (cons '() elts)
            (let ((left-size (quotient (- n 1) 2)))
                (let ((left-result (partial-tree elts left-size)))
                    (let ((left-tree (car left-result))
                          (non-left-elts (cdr left-result))
                          (right-size (- n (+ left-size 1))))
                        (let ((this-entry (car non-left-elts))
                              (right-result (partial-tree (cdr non-left-elts)
                                                          right-size)))
                            (let ((right-tree (car right-result))
                                  (remaining-elts (cdr right-result)))
                                (cons (make-tree this-entry left-tree right-tree)
                                      remaining-elts))))))))
    (car (partial-tree elements (length elements))))

(define (union-set set1 set2)
    (cond ((and (null? set1) (null? set2)) '())
          ((null? set1) set2)
          ((null? set2) set1)
          (else
            (let ((x1 (car set1)) (x2 (car set2)))
                (cond   ((= x1 x2)
                            (cons x1 (union-set (cdr set1) (cdr set2))))
                        ((< x1 x2)
                            (cons x1 (union-set (cdr set1) set2)))
                        ((> x1 x2)
                            (cons x2 (union-set set1 (cdr set2)))))))))

(define (intersection-set set1 set2)
    (if (or (null? set1) (null? set2))
        '()
        (let ((x1 (car set1)) (x2 (car set2)))
            (cond   ((= x1 x2)
                        (cons x1
                              (intersection-set (cdr set1) (cdr set2))))
                    ((< x1 x2)
                        (intersection-set (cdr set1) set2))
                    (else
                        (intersection-set set1 (cdr set2)))))))

(define (intersection-tree tree another)
    (list->tree
        (intersection-set (tree->list-2 tree)
                          (tree->list-2 another))))

(define (union-tree tree another)
    (list->tree
        (union-set (tree->list-2 tree)
                   (tree->list-2 another))))


(display (intersection-tree (list->tree '(1 2 3 4 5))
                            (list->tree '(1 3 5 7 9))))
(newline)
(display (union-tree (list->tree '(1 2 3 4 5))
                     (list->tree '(1 3 5 7 9))))

(display "\n========================================\n")
